
package main.old.new_2023.last.month_8;


import java.util.*;

/**
 * @Description: todo 1267. 统计参与通信的服务器
 * 这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。
 * 如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。
 * 请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。
 *
 * todo 841. 钥匙和房间
 * 有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。
 * 然而，你不能在没有获得钥匙的时候进入锁住的房间。
 * 当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。
 * 你可以拿上所有钥匙去解锁其他房间。
 * 给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
 *
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0824 {

    //钥匙和房间
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        //队列保存钥匙，set存储开过的房间
        Deque<Integer> keys = new ArrayDeque<>();
        keys.offer(0);
        Set<Integer> findRooms = new HashSet<>();
        while (!keys.isEmpty()){
            Integer key = keys.pop();
            if (!findRooms.contains(key)){
                findRooms.add(key);
                List<Integer> findKeys = rooms.get(key);
                if (findKeys.size() >0){
                    keys.addAll(findKeys);
                }
            }
        }
        return findRooms.size() >= rooms.size();
    }

    //统计参与通信的服务器
    public int countServers(int[][] grid) {
        int sum = 0;
        //转换为枞
        int[][] temp = new int[grid[0].length][grid.length];
        //做标记
        ArrayDeque<int[]> queues = new ArrayDeque<>();
        for (int i=0;i<grid.length;i++){
            int count = 0;
            for (int j = 0;j<grid[0].length;j++){
                if (grid[i][j] ==1){
                    temp[j][i] = grid[i][j];
                    count++;
                    queues.offer(new int[]{i,j});
                }
            }
            if (count >1){
                sum +=count;
                while (!queues.isEmpty()){
                    int[] point = queues.poll();
                    grid[point[0]][point[1]] = -1;
                }
            }else {
                queues.clear();
            }
        }
        for (int i=0;i<temp.length;i++){
            int count = 0;
            int sumCount = 0;
            for (int j = 0;j< temp[0].length;j++){
                if (temp[i][j] ==1){
                    count++;
                    if (grid[j][i] == -1){
                        sumCount ++;
                    }
                }
            }
            if (count >1){
                sum =sum + count - sumCount;
            }
        }
        return sum;
    }

}
